/**
 * 链表
 * 类似于数组
 * 但不同于数组的是，链表的数据在内存中并不是连续的
 * 链表的数据由一个存储元素本身的节点和一个指向下一个元素地址的指针构成
 * 相对于传统的数组，链表的一个好处在于
 * 添加或移除元素的时候不需要移动其他元素
 * 数组可以直接访问任何位置的任何元素
 * 而链表需要从起点(表头)开始迭代列表，直到找到所需的元素
 *
 * 链表类似寻宝，有一个线索，这个线索可以知道下一个线索的位置，
 * 这样一个一个找下去，直到找到宝藏。
 */

function LinkedList(){

  /**
   * 链表元素的构造函数
   * @param {Any} element 元素本身
   */
  var Node = function(element){
    this.element = element;
    this.next = null;
  }

  var head = null; // 链表头
  var length = 0;  // 链表的长度

  this.append = function(element) {
    var node = new Node(element);
    if(head === null){
      head = node;
    } else {
      var current = head;
      while(current.next){
        current = current.next;
      }
      current.next = node;
    }
    return ++length;
  }

  this.insert = function(element, position = 0) {
    if(position >= length) {
      return this.append(element);
    } else if (position < 0) {
      console.error(`position can't be negative`);
      return false;
      
      // 或者可以处理成下面的样子
      
      if(length === 0){ // 防止进入下面的循环后出不来
        return this.append(element);
      }

      while(position < 0) {
        position += length;
      }
    }

    var node = new Node(element);
    var current = head;
    var previous = null;

    for(var i = 0; i < position; i++){
      previous = current;
      current = current.next;
    }
    
    node.next = current;
    if (!previous){
      head = node;
    } else {
      previous.next = node;
    }
    
    return ++length;
  }

  this.removeAt = function(position){
    if(position >= length || position < 0){
      console.warn('超出范围');
      return null;
    } else {
      var current = head;
      var previous = null;
      if(position === 0){
        head = current.next;
      } else {
        for(var i = 0; i < position; i++){
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      length--;
      return current.element;
    }
  }

  // this.remove = function(element){
  //   if(length === 0){
  //     console.warn('链表为空，没有元素可移除');
  //     return null;
  //   }

  //   var current = head;
  //   var previous = null;

  //   for(var i = 0; i < length; i++){
  //     if(current.element === element){

  //       if(!previous){
  //         head = current.next;
  //       } else {
  //         previous.next = current.next;
  //       }

  //       length--;
  //       return i;
  //     }
  //     previous = current;
  //     current = current.next;
  //   }
  // }
  this.remove = function(element){
    this.removeAt(this.indexOf(element));
  }

  this.indexOf = function(element){
    var current = head;
    var i = 0;
    while(current){
      if(current.element === element){
        return i;
      }
      current = current.next;
      i++;
    }
    return -1;
  }

  this.isEmpty = function(){
    return length === 0;
  }

  this.size = function(){
    return length;
  }

  this.clear = function(){
    head = null;
    length = 0;
  }

  this.toString = function(){
    var str = '';
    var current = head;
    while(current){
      str += current.element;
      current = current.next;
    }
    return str;
  }

  this.getHead = function(){
    return head;
  }

}